package com.person.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 46.全排列
 * 2022-10-13 11:20:50
 **/
public class Sequence_0046_Permutations {
    Sequence_0046_Permutations() {

    }

    public static void main(String[] args) {
        Solution solution = new Sequence_0046_Permutations().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        private List<List<Integer>> ans = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {
            //1.如何遍历 已定序列和未定数组
            //1  2 3 4->
            //1 2  3 4->
            //1 2 3 4
            List<Integer> source = Arrays.stream(nums).boxed().collect(Collectors.toList());
            generate(source, new ArrayList<Integer>());
            return ans;
        }

        //暴力破解
        public void generate(List<Integer> source, List<Integer> target) {
            if (source.isEmpty()){
                ans.add(new ArrayList<>(target));
                return;
            }
            int i = 0;
            while(!source.isEmpty() && i<source.size()){
                target.add(source.get(i));
                ArrayList<Integer> newSource = new ArrayList<>(source);
                newSource.remove(i);
                generate(new ArrayList<>(newSource),target);
                target.remove(target.size()-1);
                i++;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}